1. Technical Field
A “Wi-Fi Multicaster” provides various techniques for implementing a network-based proxy server that performs various functions including client association, rate control and optional redundancy optimization for enabling efficient and reliable multicasting in a Wi-Fi network to potentially large numbers of clients using feedback from a “client proxy” software component running on each of the multicast clients.
2. Related Art
Multimedia IP multicast applications, such as live lecture broadcasts, are increasingly being used in enterprise and campus networks. For example, in a recent enterprise traffic study, 5-10% of all payload bytes were attributed to multicast streaming. At the same time, an increasingly large number of hosts in enterprise environments are using Wi-Fi for their basic connectivity. Thus, it would be useful for enterprise Wi-Fi networks to efficiently support IP multicasts.
Unfortunately, the peculiarities of widely adopted IEEE 802.11 protocols create several well-known problems with respect to multicasting. First, the existing 802.11 protocol does not require an ACK for multicast transmissions. Consequently, lost multicast packets are not retransmitted at the MAC layer, and some of the receivers can experience high loss rates. Second, since there are no ACKs, the MAC-level sender (generally, the access point (AP)) does not know whether any particular frame might have collided with another frame and thus, does not implement backoffs, thus resulting in unfairness to other unicast clients that do implement backoff protocols. Third, the link data rate is static and, in order to guarantee coverage to all associated clients, is typically fixed to one of the low basic rates available (e.g. ⅙ Mbps for 802.11b/g). This limits the rate at which multicast data can be sent. For example, high-definition video cannot be sent via conventional multicast protocols. Fourth, the low link data rate coupled with the packet-fair Wi-Fi MAC can significantly reduce the throughput of any contending unicast client. This is known as the “rate-anomaly problem”. Fifth, background multicast chatter can reduce energy savings for clients operating in power-save mode (PSM), since clients that are not subscribed to any multicast group have to wake up unnecessarily to receive these packets.
These problems are so severe, that many organizations simply do not permit multicast traffic over Wi-Fi links. One simple approach that has been examined as a possible solution to these problems is to convert the multicast traffic into a group of unicast sessions, one for each client. Since unicast packets are acknowledged and are subject to retransmission and rate adaptation by the AP, lower losses are observed in combination with better MAC fairness and effective high data rate transmission for the multicast stream. Unfortunately, this simple approach requires very large bandwidth capabilities (given multiple clients), thus defeating the very purpose of multicast.
In wired networks, multicast problems are often solved using application level multicasting. However, such solutions are not considered feasible for use in Wi-Fi networks. As a result, a number of solutions have been proposed for multicast in Wi-Fi networks. However, most of these solutions require significant changes to the 802.11 protocol, making it difficult, if not impossible, to deploy such solutions in the real world given the wide, almost universal, adoption of the 802.11 protocol and associated hardware. Even prototyping such solutions can be difficult since conventional 802.11-based hardware is designed to operate within the existing 802.11 protocol, and thus most of them have been evaluated via analysis or simulations only.
For example, some of the specific problems identified with respect to Wi-Fi multicasting include maximizing the number of users (MNU), balancing the load among APs (BLA), and minimizing the load of APs (MLA). These NP-hard problems have typically been addressed using approximate centralized and distributed algorithms, with only simulations being used to evaluate the performance of these algorithms. Unfortunately, such algorithms are generally restricted to the case where each user may subscribe to only one multicast flow.
Rate adaptation for broadcast/multicast is a difficult problem because of the lack of ACK-based feedback in broadcast/multicast transmissions. On the other hand, enabling ACKs for multicast would result in an ACK explosion problem, with a large increase in the MAC overhead and the need for sophisticated schemes to coordinate the ACKs sent by the clients of the multicast group. Several projects have suggested various techniques for solving the feedback problem. Unfortunately, these solutions require changing the 802.11 MAC. Consequently, given the many millions of hardware devices deployed using existing 802.11 standards, such changes to the 802.11 MAC would generally require replacing the existing 802.11 AP hardware and could leave potentially millions of existing clients without the multicast capabilities offered by changing the 802.11 MAC.
For example, in one such proposed solution, the sender sends a Request to Send (RTS) addressed to all its groups' members and waits to receive a Clear to Send (CTS) signal from them. As long as the sender is able to decode the CTS or detects that the channel is busy during the expected CTS time interval, it proceeds with the data transmission. In a related scheme, the feedback problem is addressed by electing a “leader” client that is responsible for generating an ACK. Packet losses at other group members are communicated by sending negative ACKs (also referred to as negative acknowledgements or “NAKs”) that may collide with the ACKs transmitted by the leader, thereby triggering retransmission by the access point. Unfortunately, apart from requiring changes to the 802.11 MAC, the aforementioned “solutions” cater only to the case of single-rate wireless LANs. Other “solutions” attempt to achieve latency broadcast in multi-rate mesh networks by assuming that the MAC layer of future wireless meshes would support rate adaptation for multicast. However, such assumptions are based on adapting proposed dual-tone-based MAC systems for designing a multi-rate MAC. In other words, such suggestions again require changes to the existing 802.11 MAC and/or to the wireless access points.
There is a large body of work with respect to the use of forward error correction (FEC) for improving multicast reliability. For example, one such scheme combines FEC with channel estimation and NAK-based feedback for retransmissions. This scheme has been shown, via simulations, to increase reliability without sacrificing channel efficiency. In another scheme, a network-based proxy is used that implements block erasure codes and NAK feedbacks from receivers to enable adaptive FEC support for multicast in collaborative computing applications. Yet another scheme suggests a FEC-based reliable multicast protocol that uses both FEC and retransmissions for use over the “MBone” (i.e., the proposed “multicast backbone”) and wireless mobile networks. Recently, yet another scheme was suggested that considered the effectiveness of using XOR-based network-coding for retransmission in wireless broadcast/multicast applications.
Several application layer multicast protocols have also been proposed, though IP multicast is not widely used in the Internet. For example, in one such proposal, data delivery occurs over an overlay multicast network consisting of end-hosts. In a related scheme, use of application-layer servers is proposed. Unfortunately, although such protocols consume lower bandwidth compared to using multiple unicast flows to every client, they are not designed for wireless multicast. For example, in a WLAN setting, forwarding data between wireless clients can unnecessarily increase airtime, since every wireless transmission goes through the AP.
Finally, there has been significant interest in improving performance of wireless multicast in the context of mobile and multi-hop wireless networks. For example, in one such scheme, multicast transmission happens over an overlay network that efficiently adapts to changes in network topology with minimal control traffic overhead. In another such scheme, extensions to 802.11 MAC have been proposed to reduce multicast packet losses using a distributed channel reservation protocol. Unfortunately, as noted above, there are serious infrastructure problems associated with requiring changes to the existing 802.11 MAC.